package com.emn.fil.defifil.candidats;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import com.emn.fil.defifil.iface.IDefi1;

public class DefiTriBerriau implements IDefi1{

	public List<Integer> trier(List<Integer> list, List<Integer> listExclu) {

		if (list != null || list.size() > 1) {
			
			Set set = new HashSet<Integer>();
			
			set.addAll(list);
			
			list = new ArrayList(set);
			
			Collections.sort(list);

			for (int i = 0; i < listExclu.size(); i++) {
				int p = 1000000;

				boolean val = false;

				while (val != true) {
					val = false;
					p = binarySearch(list, listExclu.get(i));
					if (p >= 0) {
						list.remove(p);
					} else {
						val = true;
					}
				}
			}
		}
				
		return list;
	}

  public static final int binarySearch(List<Integer> array, int key) {

		int min = 0, max = 0 + array.size() - 1;
		int minVal = array.get(min), maxVal = array.get(max);

		int nPreviousSteps = 0;

		for (;;) {

			if (key <= minVal)
				return key == minVal ? min : -1 - min;
			if (key >= maxVal)
				return key == maxVal ? max : -2 - max;

			assert min != max;

			int pivot;
			if (nPreviousSteps > 2) {
				pivot = (min + max) >> 1;
			} else {
				pivot = min
						+ (int) ((key - (float) minVal)
								/ (maxVal - (float) minVal) * (max - min));
				nPreviousSteps++;
			}

			int pivotVal = array.get(pivot);

			if (key > pivotVal) {
				min = pivot + 1;
				max--;
			} else if (key == pivotVal) {
				return pivot;
			} else {
				min++;
				max = pivot - 1;
			}
			maxVal = array.get(max);
			minVal = array.get(min);
		}
	}
}
